package leetcode_141_160;

import java.util.ArrayList;
import java.util.List;

public class maxProduct_152 {
    /**
     * 请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
     * 测试用例的答案是一个 32-位 整数。
     * 子数组 是数组的连续子序列。
      */
    public int maxProduct(int[] nums) {
        /**
         * 如果包含有0，那么以0为分隔点，分隔出子数组
         * 计算这些子数组中的最大乘积
         * 不包含0的数组,考虑两种情况
         * 1，奇数个负数
         * 计算最大的两个包含偶数个奇数的子数组乘积
         * 2，偶数个负数
         * 直接计算整个子数组
         * 虽然写的非常繁琐
         * 但是0ms
         */
        if(nums.length==1)
            return nums[0];
        int ans=Integer.MIN_VALUE;
        boolean flag=false;      //含有0
        for(int i=0;i<nums.length;){
            while (i<nums.length && nums[i]==0){  //跳过0
                i++;
                flag=true;
            }
            if(i==nums.length)
                break;
            int count=0;    //负数的数量
            int start=i;   //当前子数组的起始下标
            //整个子数组的积
            int multi=1;
            while (i<nums.length && nums[i]!=0){
                multi*=nums[i];
                if(nums[i]<0){
                    count++;
                }
                i++;
            }
            if(count%2==0){
                ans=Math.max(ans,multi);
            }else if(start==i-1)
                    ans=Math.max(ans, multi);
            else {
                int left=1;      //第一个负数左边那部分的乘积
                int right=1;    //最后一个负数右边那部分的乘积
                int l=start,r=i-1;
                while(l<=i-1){
                    left *= nums[l];
                    if(nums[l++]<0)
                        break;
                }
                while(r>=start){
                    right*=nums[r];
                    if(nums[r--]<0)
                        break;
                }
                int res=multi/(Math.max(left, right));
                ans = Math.max(ans, res);
            }
        }
        if(flag && ans<0)
            return 0;
        return ans;
    }


    /**
     * 评论区和我一样的思路，但是如此简洁
     */
    public int maxProduct2(int[] nums) {
        int a=1;
        int max=nums[0];

        for(int num:nums){
            a=a*num;
            if(max<a)max=a;
            if(num==0)a=1;
        }
        a=1;
        for(int i=nums.length-1;i>=0;i--){
            a=a*nums[i];
            if(max<a)max=a;
            if(nums[i]==0)a=1;
        }
        return max;
    }

    /**
     * 高解动态规划
     * 非常简洁的思路
     * 1ms,不如我
     */
    public int maxProduct3(int[] nums) {
        int max=Integer.MIN_VALUE;//结果最大值
        int imax=1;int imin=1;//阶段最大值 阶段最小值
        for(int tmp:nums)
        {
            //当遇到负数的时候进行交换，因为阶段最小*负数就变阶段最大了，反之同理
            if(tmp<0){
                int exc=imax;imax=imin;imin=exc;
            }
            //在这里用乘积和元素本身比较的意思是：
            //对于最小值来说，最小值是本身则说明这个元素值比前面连续子数组的最小值还小。相当于重置了阶段最小值的起始位置
            imax=Math.max(imax*tmp,tmp);
            imin=Math.min(imin*tmp,tmp);
            //对比阶段最大值和结果最大值
            max=Math.max(imax,max);
        }
        return max;
    }
}
